Binary Search

发表于 | 分类于 | | 热度: ℃
字数统计: 3,784 | 阅读时长 ≈ 15

0x00 算法原理

二分检索法（Binary Search)又称为折半检索，其基本思想是设字典中的元素从小到大有序地存放在数组中，然后进行折半查找，基本流程如下：

  • 首先将给定值key与字典中间位置上元素的关键码(key)比较，如果相等，则检索成功；

  • 否则，若key小，则在字典前半部分中继续进行二分法检索;

  • 若key大，则在字典后半部分中继续进行二分法检索。

  • 这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。

  • 偶数个取中间2个其中任何一个作为中间元素

二分法检索是一种效率较高的检索方法，要求字典在顺序表中按关键码排序。

0x01 算法框架

二分算法的基本框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target){
	int left = 0, right = ....
	
	while(...){
		int mid = (left + right) / 2;
		if(nums[mid] == target){
			...
		}else if(nums[mid] > target){
			right = ...
		}else if(nums[mid] < target){
			left = ..
		}
	}
	return ...
}

在使用二分法按照要求寻找目标时，一般使用else if结构而非else结构，这样可以对所有可能出现的情况进行合理分析，避免出现遗漏或重复，提高对应算法的运行效率。

参考题目

LeetCode-704.Binary Search

0x02 基本问题

下面结合前一部分提到的算法框架对常见的二分查找问题进行合理分析，尤其对算法细节进行强调，提高程序的编写效率。

寻找指定数字——最基本的二分搜索

最基本的二分搜索就是给定一个经过排序的数字数组，在其中寻找指定的数字。如果可以找到则返回其索引，否则返回-1。该类问题一般会提供一个已经按照升序完成排序的数组，如果没有提供则需要调用特定的排序方法或编写相应函数进行排序。程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binarySearch(int[] nums, int target){
	int left = 0;
	int right = nums.length-1; // 确定搜索区间类型
	
	while(left <= right){
		int mid = (left + right) / 2;
		if(nums[mid] == target){
			return mid;
		}
		else if (nums[mid] < target){
			left = mid + 1; // 结合搜索区间类型进行边界移动
		}
		else if(nums[mid] > target){
			right = mid - 1;
		}
	}
	return -1;
}

搜索区间

采用二分法进行搜索过程中，一般有两种处理方法。第一种方法即为上述定义过程，令右边界为right = nums.length-1，这样右边界即为数组最后一个元素对应下标，实际搜索范围是[left ,right]，我们将这样的区间定义为搜索区间。第二种方法为令右边界为right = nums.length，右边界为数组长度，实际搜索范围是[left, right)。

循环条件

对于以上两种处理方法，我们考虑二分终止的条件。对于第一种闭区间的搜索过程，当left == right时，搜索区间变为[left, right]，还需要再进行一次比较。其停止条件自然变为left > right，故循环条件为while(left <= right)。对于第二种左闭右开区间的搜索过程，当left == right时，搜索区间变为[left, left)，显然为空，故循环条件为while(left < right)。

边界移动

对于上述两种处理方法，有不同的边界移动方法。如果在闭搜索区间搜索，则左边界移动代码为left = mid + 1，右边界移动代码为right = mid - 1。这是因为如果边界需要移动，则说明nums[mid]与target完成比较且比较结果为不等，这样就不需要二次进行比较，我们的比较区间就变为[mid+1, right]和[left, mid-1]。

同理，如果在左闭右开区间内搜索，则左边界移动代码为left = mid + 1，此时右边界移动代码就变成了right = mid。

算法缺陷

该算法在面对寻找目标数组边界问题时具有缺陷。例如给出有序数组nums = [1,2,2,2,2,3]， target = 2，要求找出目标对应的子数组左边界，即该有序数组中第一个目标2出现的位置。在这一例中如果使用上述算法会得到2,而非nums中第一个2出现的索引1。这就是下面提到的两个基本问题。

寻找左侧边界的二分搜索

寻找左侧边界的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int left_bound(int[] nums, int target){
    if(nums.length == 0) return -1;
    int left = 0;
    int right = nums.length;
    
    while(left < right){
        int mid = (left + right) / 2;
        if(nums[mid] == target){
            right = mid;
        }
        else if (nums[mid] < target){
            left = mid + 1;
        }
        else if(nums[mid] > target){
            right = mid;
        }
    }
    if(left == nums.length) return -1;
    // 由于当left == right时，并没有进行nums[left]与target之间的比较，所以补充比较代码
    return nums[left] == target ? left: -1;
}

上述代码中的关键代码即为：if(nums[mid] == target) {right = mid;}。当发现符合target的元素时并不立即返回，而是缩小搜索区间的上界right，在区间[left, mid)中继续完成搜索，即不断向左收缩，从而达到锁定左侧边界的目的。

左侧边界换一种说法即为数组nums中小于target的元素数量。例如对有序数组nums = [2,3,5,6,8]，取target = 1，算法会返回0，说明数组中小于1的元素有0个；若令target = 10，算法返回5，说明数组中小于10的元素有5个。这样变量left的取值范围是[0, nums.length]，于是添加倒数第三行代码实现：当target比数组中所有元素都大时返回-1。

值得注意的是，如果目标元素target比有序数组nums中所有的元素都大，此时满足left == nums.length即二分的右边界未发生移动。我们直接使用return -1;语句执行跳出，否则在进行其他深入查找时容易出现数组下标越界的错误。

寻找右侧边界的二分搜索

先上搜索代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int right_bound(int[] nums, int target){
    if(nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while(left < right){
        int mid = (left + right) / 2;
        if(nums[mid] == target){
            left = mid + 1;
        }
        else if(nums[mid] < target){
            left = mid + 1;
        }
        else if(nums[mid] > target){
            right = mid;
        }
    }
    if(left == 0) return -1;
    return nums[left-1] == target ? (left-1) : -1;
}

上述代码的关键部分为left = mid + 1，即当nums[mid] == target时并不立即返回，而是增大搜索区间的下界left，使得区间不断向右收缩，达到锁定右侧边界的目的。

由于对left值的更新采用语句left = mid + 1，就是说while循环结束时，nums[left]一定与target不相等，而nums[left-1]与target可能相等，所以最终返回的结果为left - 1而不是left的值。

值得注意的是，如果目标元素target比有序数组nums中所有的元素都小，此时满足left == 0即二分的左边界未发生移动。我们直接使用return -1;语句执行跳出，否则在进行其他深入查询时容易出现数组下标越界的错误。

0x03 模板

模板I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

区分语法

  • 初始条件：left = 0, right = length-1
  • 终止条件： left > right
  • 向左查找： right = mid - 1
  • 向右查找： left = mid + 1

参考题目

LeetCode-60.Sqrt(x)

该题目也可以使用牛顿迭代法求解，速度更快

LeetCode-33.Search in Rotated Sorted Array

模板II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length;
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.length && nums[left] == target) return left;
  return -1;
}

区分语法

  • 初始条件： left = 0, right = length
  • 终止条件： left == right
  • 向左查找： right = mid
  • 向右查找：left = mid + 1

关键属性

  • 保证查找空间在每一步中至少有2个元素
  • 需要进行后续处理，当剩下1个元素时，循环/递归结束，需要评估剩余元素是否符合条件

参考题目

LeetCode-162.Find PeakElement

LeetCode-153.Find Minimum in Rotated Sorted Array

模板III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

关键属性

  • 保证查找空间在每个步骤中至少有3个元素
  • 需要进行后续处理。当剩下两个元素时，循环/递归结束，需要评估其余元素是否符合条件

区分语法

  • 初始条件： left = 0, right = length - 1
  • 终止条件：left + 1 == right
  • 向左查找：right = mid
  • 向右查找：left = mid

参考题目

LeetCode-658.Find K Closest Elements

LeetCode-34.Find First and Last Position of Element in Sorted Array

0x04 二分查找与三分查找

对于二分查找，其时间复杂度为O(logn)(base2)，空间复杂度为O(1)，没有使用额外的空间。

对于三分查找，其时间复杂度为O(logn)(base3)，空间复杂度为O(1)，没有使用额外的空间。

看上去三分查找的时间复杂度更低，也就是说效率比二分查找更高，但如果我们求出最坏情况下两者的渐近复杂度，就可以看到三分查找的效果其实不如二分查找。

二分查找最坏情况下的渐近复杂度：

2.PNG-21.1kB

三分查找最坏情况下的渐近复杂度：

3.PNG-20.6kB

如果需要比较两个渐近复杂度，我们只需要比较$\log_2 n$与$2\log_3n$的大小关系。表达式$2\log_3 n$可以被写作$2/(\log_2 3)*\log_2 n$，因此$2/(\log_2 3)$比1大，所以最坏情况下三分查找比较次数大于二分查找。

参考题目

LeetCode-374.Guess Number Higher or Lower

0x05 总结

二分法标志

  • 题目给出一个或多个有序或半有序数组
  • 查找数组中一个或多个符合要求的特定元素
  • 时间复杂度要求对数级别即O(logn)

二分查找要点

  • 结合题目抽象出左右边界

    对于只需要查找单个元素的有序数组，数组的第一个和最后一个元素即为左右边界；

    对于需要查找单个元素的半有序或无序数组，将数组排序后情况同上；

    对于求数组中各元素的距离（元素之差）或部分元素和（最小子数组元素和）等在查找条件上“二次加工”的题目需要根据题目意图抽象出左右边界，即符合题目要求的合理范围。

  • 循环及跳出条件

    循环入口点使用while(left < right)语句，使用该语句的优点是退出循环时无需考虑返回left或right值（此时二者相等），但是在某些情况下需要对nums[left]再进行一次比较（未取到该边界）。

  • 边界移动条件

    该部分为二分查找方法的关键部分，结合题目找出保留一半，排除一半的边界条件。对于符合要求的特定元素查找，首先判断是否为该元素，如果是则直接返回该元素对应的结果；否则就需要进行边界移动。对于涉及到返回边界的问题，需要使用减治法进行查找，从而保证每次边界移动会排除一定不符合要求的部分。

  • 边界移动与取中间数的对应关系

    对于取中间数的语句，一般会想到mid = (left + right) / 2，但该语句存在溢出的风险即可能得到不符合要求的中间值，我们使用mid = left + (right - left) / 2，该语句中最大值从left + right变成了right - left，相应减少了溢出的风险。为了进一步保证运算的准确性，可以使用位移动符号来代替除法。Java语言中提供无符号右移>>>，使用无符号右移对操作数右移之后，不论这个数正负与否，高位一律补0.这样即使left + right整形溢出，得到的结果依然正确，并且具有更高的运算效率。综上我们使用mid = (left + right) >>> 1作为取中位数的语句。

    为了不产生死循环的状况，我们将边界移动与取中间数进行对应，提供两种参考方法。

    方法一：mid被分配到左边，将区间分成[left, mid]和[mid+1, right]，此时中间数向下取整。

    1
    2
    3
    4
    5
    6
    7
    int mid = (left + right) >>> 1;
    if(check(mid)){
        // 下一轮搜索区间是[left, mid]
        right = mid;
    }else{
        left = mid + 1;
    }

    方法二：mid被分配到右边，将区间分成[left, mid-1]和[mid, right]，此时中位数向上取整。

    1
    2
    3
    4
    5
    6
    7
    int mid = (left + right + 1) >>> 1;
    if(check(mid)){
        // 下轮搜索区间为[left, mid-1]
        right = mid - 1;
    }else{
        left = mid;
    }

    这两个方法可以简单记为：left = mid时向上取整，left = mid + 1时向下取整。

一般步骤

  • 确定搜索区间初始化时候的左右边界，需要关注一下边界值
  • 无条件写上while(left < right)，退出循环的条件是left == right，无需考虑返回边界类型
  • 先写下取整的中间数取法，然后从如何把mid排除掉的角度思考if和else语句应该如何编写，在if语句有把握写对的情况下，else就是if的反面，可以直接编写。这种写法把待搜索区间从逻辑上分成两个区间，一个区间不可能存在目标元素，则只需要在另一个区间内继续搜索，更符合”二分”的语义。
  • 根据if-else中的边界移动行为，观察是否需要修改取中间数的行为，如果需要则进行对应修改。
  • 退出循环时，一定有left == right成立，有些时候可以直接返回left，但有些时候还需要再完成一次判断，判断left与right是否为需要查找的元素，这一步称为后续处理。

0x06 典型题目

LeetCode-154.Find Minimum in Rotated Sorted Array II

LeetCode-4.Median of Two Sorted Arrays

LeetCode-410.Split Array Largest Sum

LeetCode-719.Find K-th Smallest Pair Distance

请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多